// 07-图6 旅游规划
#include <stdio.h>
#include <stdlib.h>

/* Array ================================*/
int **init2D(int n) {
    int** a = (int**) calloc(sizeof(int*), n);
    for (int i=0; i<n; i++) {
        a[i] = (int*) calloc(sizeof(int), n);
    }
    return a;
}

void free2D(int **a, int n) {
    for (int i=0; i<n; i++) {
        free(a[i]);
    }
    free(a);
}

void print2D(int **m, int n, int defaultWeight) {
    for (int i=-1; i<n; i++) {
        printf("[%3d]", i);
    }
    printf("\n");
    for (int i=0; i<n; i++) {
        printf("[%3d]", i);
        for (int j=0; j<n; j++) {
            if (m[i][j] == defaultWeight) {
                printf("    -");
            } else {
                printf("%5d", m[i][j]);
            }
        }
        printf("\n");
    }
}

/* MGraph ===============================*/
// 定义权重的最大值
#define MaxWeight 0x7FFF
// 无路径
#define Connectionless -1
// 有向图, 无向图
#define DirectedGraph 1
#define UndirectedGraph 0

// 权重类型
typedef int WeightType;
typedef struct Edge Edge;
struct Edge {
    int v, w;
    WeightType weight;
};

typedef struct MGraph MGraph;
struct MGraph {
    int directed; // 1-有向图，0-无向图
    int defaultWeight; // 默认的无连接的权重
    int vertexNum; // 顶点数
    int edgeNum;   // 边数
    WeightType **g; // 邻接矩阵
};

Edge createEdge(int v, int w, int weight) {
    Edge e;
    e.v = v;
    e.w = w;
    e.weight = weight;
    return e;
}

MGraph *createGraph(int directed, int defaultWeight, int vertexNum) {
    MGraph* g = (MGraph*)calloc(sizeof(MGraph), 1);
    g->directed = directed;
    g->defaultWeight = defaultWeight;
    g->vertexNum = vertexNum;
    // 初始化邻接矩阵
    g->g = (WeightType**) malloc(sizeof(WeightType*) * vertexNum);
    for (int v=0; v < g->vertexNum; v++) {
        g->g[v] = (WeightType*) malloc(sizeof(WeightType) * vertexNum);
        for (int w=0; w < g->vertexNum; w++) {
            g->g[v][w] = defaultWeight;
        }
    }
    return g;
}

void freeGraph(MGraph* g) {
    free2D(g->g, g->vertexNum);
    free(g);
}

// 判断图的两个顶点 v1, v2 之间是否有直接连接
int isConnection(MGraph* g, int v1, int v2) {
    return g->g[v1][v2] != g->defaultWeight;
}

void insertEdge(MGraph* g, int v1, int v2, WeightType weight) {
    g->g[v1][v2] = weight;
    if (g->directed == UndirectedGraph) {
        g->g[v2][v1] = weight;
    }
}

void printGraph(MGraph* g) {
    printf("Graph n=%d, e=%d\n", g->vertexNum, g->edgeNum);
    print2D(g->g, g->vertexNum, g->defaultWeight);
}

/* Dijkstra =====================================================*/
// 找到未被收录顶点中dist最小的顶点
int findMinDist(MGraph* g, int dist[], int collected[]) {
    int minV = -1;
    int minDist = MaxWeight;
    for (int v=0; v < g->vertexNum; v++) {
        if (!collected[v] && dist[v] < minDist) {
            // 未收录，且dist[v]更小
            minDist = dist[v];
            minV = v;
        }
    }
    // 返回找到的顶点，若没找到，返回的就是初始值-1
    return minV;
}

/**
 * 单源最短路径算法
 * g 图
 * costMatrix 花费权重
 * path 计算得到的路径
 * dist 计算得到的距离
 * cost 计算得到的花费
 * s 开始节点
*/
int dijkstra(MGraph* g, WeightType** costMatrix, int path[], int dist[], int cost[], int s) {
    int* collected = (int*) calloc(g->vertexNum, sizeof(int));
    // 初始化
    for (int v=0; v < g->vertexNum; v++) {
        dist[v] = g->g[s][v];
        cost[v] = costMatrix[s][v];
        if (dist[v] < MaxWeight) {
            path[v] = s;
        } else {
            path[v] = Connectionless;
        }
        collected[v] = 0;
    }
    // 先把起点收入
    collected[s] = 1;
    dist[s] = 0;

    for (;;) {
        // 找到未被收录顶点中dist最小的顶点
        int v = findMinDist(g, dist, collected);
        if (v == -1){
            break;
        }
        collected[v] = 1; // 收录v
        for (int w=0; w < g->vertexNum; w++) {
            if (g->g[v][w] < 0) {
                // 有负边，算法不支持，退出
                free(collected);
                return 0;
            }
            // 对 v 的每个未收录的邻接点 w
            if (!collected[w] && g->g[v][w] < MaxWeight) {
                if (dist[v] + g->g[v][w] < dist[w]) {
                    // 找到最短路径
                    dist[w] = dist[v] + g->g[v][w];
                    cost[w] = cost[v] + costMatrix[v][w];
                    path[w] = v;
                } else if (dist[v] + g->g[v][w] == dist[w] && cost[v] + costMatrix[v][w] < cost[w]) {
                    // 路径相等，花费不同
                    cost[w] = cost[v] + costMatrix[v][w];
                    path[w] = v;
                }
            }
        }
    }
    free(collected);
    return 1;
}
// #include "../base/MGraph-Dijkstra.c"

/* current ======================================================*/
MGraph* buildGraph(int vertexNum, int edgeNum, WeightType** costMatrix) {
    MGraph* g = createGraph(UndirectedGraph, MaxWeight, vertexNum);
    for (int i=0; i<edgeNum; i++) {
        int v1, v2;
        WeightType dist, cost;
        scanf("%d %d %d %d", &v1, &v2, &dist, &cost);
        insertEdge(g, v1, v2, dist);
        costMatrix[v1][v2] = costMatrix[v2][v1] = cost;
    }
    return g;
}

int main() {
    int n, m, s, d;
    scanf("%d %d %d %d", &n, &m, &s, &d);

    WeightType** costMatrix = init2D(n);
    MGraph* g= buildGraph(n, m, costMatrix);
    // printGraph(g);

    WeightType *dist = (WeightType*) calloc(n, sizeof(WeightType));
    WeightType *cost = (WeightType*) calloc(n, sizeof(WeightType));
    int *path = (int*) calloc(n, sizeof(int));
    dijkstra(g, costMatrix, path, dist, cost, s);
    printf("%d %d\n", dist[d], cost[d]);

    freeGraph(g);
    free2D(costMatrix, n);
    free(dist);
    free(cost);
    free(path);
    return 0;
}
